from functools import lru_cache
from functools import reduce

__all__ = ["chinese_remainder", "exgcd", "gcd", "gcd_list",
        "inv_mod", "lcm"]


def gcd(m, n):
    m = abs(m)
    n = abs(n)
    while m:
        m, n = n % m, m
    return n


def gcd_list(iterable):
    g = 0
    for x in iterable:
        g = gcd(g, x)
        if g == 1:
            return 1
    return g


def lcm(m, n):
    if not m or not n:
        return 0
    else:
        return m // gcd(m, n) * n


def lcm_list(iterable):
    return reduce(lcm, iterable, 1)


def exgcd(m, n):
    a1 = 0
    a2 = 1
    b1 = 1
    b2 = 0
    while m:
        (q, m), n = divmod(n, m), m
        a1, a2 = a2, a1 - q * a2
        b1, b2 = b2, b1 - q * b2
    return (n, a1, b1) if n >= 0 else (-n, -a1, -b1)


@lru_cache()
def inv_mod(m, n):
    x = exgcd(m, n)[1]
    return x if x >= 0 else n + x


def chinese_remainder(array):
    m = 1
    y = 0
    for remainder, mod in array:
        y += m * ((remainder - y) * inv_mod(m, mod) % mod)
        m *= mod
    return y
